package 数据结构专栏.A_二叉树专栏.D_路径问题;

import 数据结构专栏.A_二叉树专栏.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Title 路径问题求解
 * @Author zhengqiang.tan
 * @Date 2021/4/17 5:03 PM
 * https://www.cnblogs.com/lishanlei/p/10707709.html
 */
public class RoadpathTest {


    public List<ArrayList<Integer>> FindPath(TreeNode root, int target) {

        List<ArrayList<Integer>> listAll = new ArrayList<>(); //保存所有符合条件的路径用于返回值
        List<Integer> list = new ArrayList<>(); //存储当前路径
        return SeekPath(listAll, list, root, target);
    }

    private List<ArrayList<Integer>> SeekPath(List<ArrayList<Integer>> listAll, List<Integer> list, TreeNode root, int target) {
        if (root == null) return listAll;
        list.add(root.val);
        target -= root.val;
        if (target == 0 && root.left == null && root.right == null) { //当前路径和是指定值且当前节点是叶子节点
            listAll.add(new ArrayList<>(list));
        }
        SeekPath(listAll, list, root.left, target);
        SeekPath(listAll, list, root.right, target);
        list.remove(list.size() - 1);  //递归回到父节点时需要在路径中删除上一个节点信息
        return listAll;
    }

    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(10);
        TreeNode t2 = new TreeNode(5);
        TreeNode t3 = new TreeNode(12);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(7);
        t1.left = t2;
        t1.right = t3;
        t2.left = t4;
        t2.right = t5;

        RoadpathTest s = new RoadpathTest();
        System.out.println(s.FindPath(t1, 22)); // [[10, 5, 7], [10, 12]]

    }

}
